I. Field of the Invention
The present invention relates generally to a method for compressing and reconstructing a data representation of a picture, and more specifically, to a method for reducing distortions of that data caused thereby.
II. Background Information
A method for compressing and reconstructing a data representation of a picture ("original picture data") employing transform coding generally includes a partitioning step, a transform coding step, a suppressing step, a decoding step, and a combining step.
In the partitioning step, the original picture data is partitioned into a plurality of input blocks, with each such input block comprising input block data representing a border of picture elements ("pixels") and interior pixels surrounded by such border pixels. Each pixel corresponds to a location in the picture represented by the original picture data, and each pixel has a value corresponding to the brightness of the picture at that location.
In the transform coding step, the data of each input block is individually transformed to obtain transformed input block data representative of a plurality of coefficients, with each such coefficient associated with spatial frequencies inherent in the input block data.
In the suppressing step, data from the transformed input block data for each input block are suppressed to obtain compressed transformed input block data. Such suppressing occurs either by discarding data representative of certain coefficients or by assigning fewer data bits to such coefficients.
The compressed transformed input block data for each input block is transmitted or stored, and subsequently either received or accessed.
In the decoding step, the compressed transformed input block data for each input block is inversely transformed to obtain output block data for each input block.
In the combining step, the output block data for adjacent input blocks is juxtaposed to obtain reconstructed picture data representative of the original picture data.
The quality of the picture represented by the reconstructed picture data depends on faithfully reproducing input block data of each input block which represents the original picture data and discarding data in the suppressing step representing only those coefficients, or assigning fewer data bits to such coefficients, which contribute least to such faithful reproduction. Coefficients associated with high frequencies ("high frequency coefficients") contribute least to the faithful reproduction of input block data of an input block as a whole, and are usually discarded, or assigned fewer data bits, although such coefficients contribute most to the faithful reproduction of input block data representing border pixels of that block.
As a result, input block data representative of border pixels of an input block is distorted by such disarding or assigning. Such distortions are reflected in the corresponding output block data. When output block data for adjacent input blocks is juxtaposed in the combining step, these distortions form discontinuous jumps in pixel values where output block data for such input blocks is juxtaposed, which in turn cause discontinuous jumps in brightness in the resultant picture represented by such juxtaposition of output block data. Such jumps in brightness are highly visible since the human eye is extremely sensitive to such discontinuous jumps, particularly when they form a straight line as is the case for block borders.
Several compressing and reconstructing methods have been advanced to reduce these discontinuous pixel value jumps and, incidentally, the discontinuous brightness jumps caused thereby. The first such method, windowing, includes a partitioning step, and immediately thereafter, a weighting step.
In the partitioning step, the original picture data is partitioned into a plurality of overlapping input blocks, with each such input block comprising input block data representative of pixels shared with adjacent input blocks.
In the weighting step, input block data representative of all pixels of an input block are weighted prior to transform coding such input block data. This weighting improves reproduction of the input block data by reducing the effect of suppressing transformed input block data in a subsequent conventional suppressing step. However, a problem with windowing is that input block data representing all pixels of an input block are weighted, and extensive and repetitive overlapping of the input blocks occurs.
Such weighting and overlapping encumber windowing with a substantial amount of computational overhead due to the repetitive transform coding and decoding of data representing pixels shared between adjacent input blocks ("overhead pixels") caused thereby. For example, M. Schlichte in Block-Overlap Transform Coding of Image Signals, Siemens Research and Dev. Rep., vol. 13, No. 3 (1984), teaches windowing with overlapping input blocks, where every pixel of each such block is shared with three adjacent input blocks, so that data representative of three times as many pixels as are represented by the original picture data are transform coded and decoded.
A compressing and reconstructing method which is not so encumbered is linear interpolation which, as described by G. Anderson and T. Huang in Piecewise Fourier Transformation for Picture Bandwidth Compression, IEEE Transactions on Com. Technology, vol. COM-19, No. 2 (April 1971), adds one row and one column of new pixels to each input block before transform coding the input block data of such block, with such new pixels having values representative of linear interpolations between the values of border pixels located on opposite sides of the input blocks ("linearly interpolated overhead pixels").
Linear interpolation is, however, of extremely limited applicability, since linear interpolation requires that the Discrete Fourier Transform ("DFT") be employed to transform the data of each input block during the transform coding step, and the DFT is not generally considered to be the optimum type transform. In addition, in many cases, even when the DFT is employed, adding only one row and one column of new linearly interpolated overhead pixels to each input block in the partitioning step will not reduce distortion of the data representative of the border pixels of a block to the extent required to eliminate visible discontinuous brightness jumps in the resultant picture.
A compressing and reconstructing method which envisages using more than one extra row and one column of overhead pixels with each input block is called averaging. In averaging, as described by H. Reeve and J. Lim in Reduction of Blocking Effects in Image Coding, Optical Engineering, vol. 23, No. 1 (Jan./Feb. 1984), the overhead pixels are not new pixels, but pixels shared between adjacent input blocks, and data representative of such pixels are averaged in the combining step. As a result, data representative of such pixels is distorted in the suppressing step, such distortions being only partially overcome by the averaging, resulting in visible discontinuous brightness jumps remaining in the resultant picture.
Accordingly, an object of the present invention is to provide a method for compressing and reconstructing original picture data which reduces discontinuous brightness jumps in the resultant picture represented by such data, but which has low computational overhead and which has wide applicability.
Additional objects and advantages of the invention will be set forth in the description which follows or may be learned by practice of the invention.